BIT Algo/3. Zajęcia/Zadanie 3. (Sprawdzanie, czy k. największy element kopca Min Heap jest większy lub równy x).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Dana jest tablica liczb rzeczywistych wielkości $ n $, reprezentująca kopiec minimum (array-based heap). Mając daną liczbę rzeczywistą $ x $, sprawdź, czy $ k. $ najmniejszy element jest większy lub równy $ x $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# I Sposób\n",
    "### (gorszy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ten algorytm polega na skorzystaniu z metody, usuwającej najmniejszą wartość z kopca. Nie wymaga on w żaden sposób przeszukiwania kopca lub wymyślania skomplikowanych algorytmów. Konieczne jest jedynie usunięcie $ k-1 $ minimalnych elementów i zwrócenie wartości $ k. $ elementu (tego, który pozostanie w korzeniu drzewa - pod zerowym indeksem tablicy)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ponieważ nie jest powiedziane, że tablica nie może zostać zmodyfikowana, możemy usuwać z niej elementy. Ja jednak wybrałem implementację kopca, która przerzuca elementy na koniec tablicy, tak, aby ich nie stracić. W poniższej implementacji ograniczam się jedynie do metod klasy, które są konieczne do wykonania tego zadania."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Przyjmuję, że nie istnieje zerowy element, a pierwszy najmniejszy element odpowiada początkowej wartości korzenia."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_kth_val_gt_or_eq_x(arr: list, k: int, x):\n",
    "    # Return None if got not valid value of k\n",
    "    if k < 1: return None\n",
    "    heap = MinHeap(arr)\n",
    "    for _ in range(k-1):\n",
    "        heap.remove_min()\n",
    "    return heap.get_min() >= x\n",
    "        \n",
    "\n",
    "class MinHeap:\n",
    "    def __init__(self, values):\n",
    "        self.heap = values\n",
    "        self.size = len(values)\n",
    "        self._free_idx = self.size\n",
    "        self.build_heap()\n",
    "    \n",
    "    def __bool__(self):\n",
    "        return bool(self._free_idx)\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self.heap)\n",
    "    \n",
    "    @property\n",
    "    def heap_size(self):\n",
    "        return self._free_idx\n",
    "    \n",
    "    @staticmethod\n",
    "    def parent_idx(curr_idx):\n",
    "        return (curr_idx - 1) // 2\n",
    "    \n",
    "    @staticmethod\n",
    "    def left_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 1\n",
    "    \n",
    "    @staticmethod\n",
    "    def right_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 2\n",
    "        \n",
    "    def get_min(self) -> object:\n",
    "        return None if not self.heap else self.heap[0]\n",
    "        \n",
    "    def remove_min(self) -> object:\n",
    "        if self.heap_size == 0:\n",
    "            raise IndexError(f'remove_min from an empty {self.__class__.__name__}')\n",
    "        # Store a value to be returned\n",
    "        removed = self.heap[0]\n",
    "        # Place the last leaf in the root position\n",
    "        self._free_idx -= 1\n",
    "        last = self.heap[self._free_idx]\n",
    "        \n",
    "        if self.heap_size > 0:\n",
    "            # Move the last element to the end of an array\n",
    "            self.heap[self._free_idx] = removed\n",
    "            self.heap[0] = last\n",
    "            # Fix a heap in order to stisfy a min-heap property\n",
    "            self._heapify_down(0, self.heap_size)\n",
    "        return removed\n",
    "    \n",
    "    def swap(self, i, j):\n",
    "        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]\n",
    "        \n",
    "    def _heapify_down(self, curr_idx, end_idx):  # O(log n)\n",
    "        # Loop till the current node has a child smaller than itself\n",
    "        # We assume that when we enter a node which both children are\n",
    "        # larger than this node, a subtree which a current node is a\n",
    "        # root of must fulfill a min-heap property\n",
    "        while True:\n",
    "            l = self.left_child_idx(curr_idx)\n",
    "            r = self.right_child_idx(curr_idx)\n",
    "            smallest_idx = curr_idx\n",
    "\n",
    "            if l < end_idx:\n",
    "                if self.heap[l] < self.heap[curr_idx]: \n",
    "                    smallest_idx = l\n",
    "                if r < end_idx and self.heap[r] < self.heap[smallest_idx]:\n",
    "                    smallest_idx = r\n",
    "\n",
    "            if smallest_idx != curr_idx:\n",
    "                self.swap(curr_idx, smallest_idx)\n",
    "                curr_idx = smallest_idx\n",
    "            else:\n",
    "                break\n",
    "                \n",
    "    def build_heap(self):   # O (n)\n",
    "        for i in range(self.heap_size // 2 - 1, -1, -1):\n",
    "            self._heapify_down(i, self.heap_size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorted arr:\n",
      "[-97, -96, -94, -93, -82, -80, -75, -51, -49, -19, -15, -2, 28, 43, 50, 55]\n",
      "x value: -72\n",
      "Expected: False \t(kth value: -80)\n",
      "Result:   False \t(kth value: -80)\n",
      "Arr after calling function:\n",
      "[-80, -75, -49, -19, -51, -2, 43, 50, 55, -15, 28, -82, -93, -94, -96, -97]\n",
      "Has an array the same elements as before?: True\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "arr = [random.randint(-100, 100) for _ in range(random.randint(1, 20))]\n",
    "k = random.randrange(1, len(arr) + 1)\n",
    "x = random.randint(-100, 100)\n",
    "\n",
    "sorted_arr = sorted(arr)\n",
    "print(\"Sorted arr:\", sorted_arr, sep='\\n')\n",
    "print('x value:', x)\n",
    "print(\"Expected:\", sorted_arr[k-1] >= x, f'\\t(kth value: {sorted_arr[k-1]})')\n",
    "print(\"Result:  \", is_kth_val_gt_or_eq_x(arr, k, x), f'\\t(kth value: {arr[0]})')\n",
    "print(\"Arr after calling function:\", arr, sep='\\n')\n",
    "print(\"Has an array the same elements as before?:\", not set(arr).symmetric_difference(sorted_arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OK!\n"
     ]
    }
   ],
   "source": [
    "for _ in range(100_000):\n",
    "    arr = [random.randint(-100, 100) for _ in range(random.randint(1, 20))]\n",
    "    k = random.randrange(1, len(arr) + 1)\n",
    "    x = random.randint(-100, 100)\n",
    "    \n",
    "    sorted_arr = sorted(arr)\n",
    "    \n",
    "    if (sorted_arr[k-1] >= x) is not is_kth_val_gt_or_eq_x(arr, k, x):\n",
    "        print('Failed for:')\n",
    "        print('k:', k)\n",
    "        print('x:', x)\n",
    "        print(arr)\n",
    "        break\n",
    "else:\n",
    "    print(\"OK!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# II Sposób\n",
    "### (najlepszy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Wstępne obserwacje"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Korzystamy z wiedzy o tym, w jaki sposób są przechowywane wartości w kopcu. Wystarczy zauważyć, że każdy rodzic w kopcu Min Heap ma oboje dzieci o wartości większej od siebie (lub równej sobie). Wystarczy zatem przeszukiwać kopiec, wybierając zawsze to poddrzewo, którego korzeń ma wartość najmniejszą. Nie jest to jednak takie proste, ponieważ może się skończyć dana gałąź i znajdziemy się w liściu, zanim zdążymy odwiedzić $ k-1 $ najmniejszych węzłów. Jest jeszcze jedna kwestia, jak stwierdzić, na której z kolei najmniejszej wartości się znajdujemy obecnie. Nie mamy przecież pewności, że wszystkie węzły, które odrzuciliśmy, wybierając np. lewe poddrzewo, są większe od tych z lewego poddrzewa. Chodzi o to, że wybranie obecnie najmniejszej wartości spośród dzieci bieżącego węzła nie daje nam gwarancji, że wśród dzieci tego węzła również będzie najmniejsza spośród pozostałych wartości. W takiej sytuacji kolejna najmniejsza spośród pozostałych może się znajdować w zupełnie innej części drzewa, reprezentującego kopiec."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Plan działania"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "W tym miejscu warto zauważyć, że najłatwiejszym rozwiązaniem jest rozwiązanie rekurencyjne. Zamiast próbować kolejno odwiedzać wartości najmniejsze, można postąpić dużo sprytniej. W poleceniu mamy podaną wartość $ x $, z którą mamy \"porównać\" k. element tablicy. Najlepszym rozwiązaniem jest odwiedzanie rekurencyjne wszystkich tych węzłów, których wartość jest mniejsza od $ x $. Zauważmy, że dużo łatwiej utworzyć funkcję rekurencyjną, która zwróci prawdę, jeżeli odwiedzony przez nas $ k. $ w kolejności węzeł będzie zawierał wartość mniejszą od $ x $, czyli nie będzie spełniał pożądanego warunku. Idea jest taka, że w rekurencyjnej funkcji dla bieżąvego węzła decydujemy, czy jest to węzeł o wartości mniejszej niż $ x $. Jeżeli nie, oznacza to, że dalsze odwiedzanie tego poddrzewa nie ma sensu, bo wszystkie kolejne wartości będą większe lub równe wartości $ x $, a my musimy jeszcze sprawdzić pozostałe węzły, czy wśród nich nie ma wartości mniejszych. Zatem zwracamy wówczas Fałsz, aby dalej nie przeglądać tego poddrzewa. Jeżeli jednak znajdujemy się w odpowiednim węźle, czyli takim, którego wartośc jest mniejsza od $ x $, zwiększamy licznik odwiedzonych węzłów o wartościach mniejszych od $ x $ o 1 i sprawdzamy, czy łączna liczba odwiedzonych przez nas węzłów wynosi $ k $, gdzie $ k $ oznacza, którą najmniejszą z kolei wartość szukamy (patrz polecenie). Jeżeli nasz licznik osiągnął wartość $ k $, oznacza to, że przejrzeliśmy dokładnie $ k $ węzłów o wartościach mniejszych niż $ x $, więc na pewno $ k. $ najmniejsza wartość nie może być większa lub równa $ x $, bo już było $ k $ wartości mniejszych. Zatem wtedy zwracamy prawdę, aby przerwać wywołania rekurencyjne. Jeżeli jednak wciąż wartość licznika jest mniejsza niż $ k $, sprawdzamy, czy bieżący węzeł ma prawe lub lewe dziecko i, jeżeli tak, przeszukujemy odpowiednie poddrzewa w sposób rekurencyjny."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nie wiem, czy to, że dostajemy tablicę, która reprezentuje kopiec, oznacza, że jej wartości są odpowiednio ułożone, jak powinny być w kopcu, więc na początku buduję kopiec."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_kth_val_gt_or_eq_x(arr: list, k: int, x):\n",
    "    # Return None if got not valid value of k\n",
    "    if k < 1: return None\n",
    "    heap = MinHeap(arr)\n",
    "    \n",
    "    # Traverse a heap till there are nodes of a value lower\n",
    "    # than x or the number of nodes which we already visited\n",
    "    # is lower than k\n",
    "    visited_count = 0\n",
    "    \n",
    "    def traverse(idx):\n",
    "        nonlocal visited_count\n",
    "        \n",
    "        if heap[idx] >= x:\n",
    "            return False\n",
    "        \n",
    "        visited_count += 1\n",
    "        if visited_count == k:\n",
    "            return True\n",
    "\n",
    "        l_idx = heap.left_child_idx(idx)\n",
    "        r_idx = heap.right_child_idx(idx)\n",
    "\n",
    "        if r_idx < heap.heap_size:\n",
    "            return traverse(l_idx) or traverse(r_idx)\n",
    "        if l_idx < heap.heap_size:\n",
    "            return traverse(l_idx)\n",
    "        \n",
    "    return not traverse(0)\n",
    "    \n",
    "\n",
    "class MinHeap:\n",
    "    def __init__(self, values):\n",
    "        self.heap = values\n",
    "        self.size = len(values)\n",
    "        self._free_idx = self.size\n",
    "        self.build_heap()\n",
    "    \n",
    "    def __bool__(self):\n",
    "        return bool(self._free_idx)\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self.heap)\n",
    "    \n",
    "    def __getitem__(self, idx: int):\n",
    "        if not isinstance(idx, int):\n",
    "            raise TypeError(f\"expected 'int', got {str(type(idx))[7:-1]}\")\n",
    "        if not 0 <= idx < self.heap_size:\n",
    "            raise IndexError(f'node index too {\"small\" if idx < 0 else \"large\"}')\n",
    "        return self.heap[idx]\n",
    "    \n",
    "    @property\n",
    "    def heap_size(self):\n",
    "        return self._free_idx\n",
    "    \n",
    "    @staticmethod\n",
    "    def parent_idx(curr_idx):\n",
    "        return (curr_idx - 1) // 2\n",
    "    \n",
    "    @staticmethod\n",
    "    def left_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 1\n",
    "    \n",
    "    @staticmethod\n",
    "    def right_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 2\n",
    "    \n",
    "    def swap(self, i, j):\n",
    "        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]\n",
    "        \n",
    "    def _heapify_down(self, curr_idx, end_idx):  # O(log n)\n",
    "        # Loop till the current node has a child smaller than itself\n",
    "        # We assume that when we enter a node which both children are\n",
    "        # larger than this node, a subtree which a current node is a\n",
    "        # root of must fulfill a min-heap property\n",
    "        while True:\n",
    "            l = self.left_child_idx(curr_idx)\n",
    "            r = self.right_child_idx(curr_idx)\n",
    "            smallest_idx = curr_idx\n",
    "\n",
    "            if l < end_idx:\n",
    "                if self.heap[l] < self.heap[curr_idx]: \n",
    "                    smallest_idx = l\n",
    "                if r < end_idx and self.heap[r] < self.heap[smallest_idx]:\n",
    "                    smallest_idx = r\n",
    "\n",
    "            if smallest_idx != curr_idx:\n",
    "                self.swap(curr_idx, smallest_idx)\n",
    "                curr_idx = smallest_idx\n",
    "            else:\n",
    "                break\n",
    "                \n",
    "    def build_heap(self):   # O (n)\n",
    "        for i in range(self.heap_size // 2 - 1, -1, -1):\n",
    "            self._heapify_down(i, self.heap_size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorted arr:\n",
      "[-72, -68, -57, -25, -24, -16, 6, 21, 23, 24, 29, 69, 74, 84, 95]\n",
      "x value: 90\n",
      "k value: 8\n",
      "Expected: False\n",
      "Result:   False\n",
      "Arr after calling function:\n",
      "[-72, -68, -57, 24, -16, -25, 21, 29, 74, 95, 6, -24, 84, 69, 23]\n",
      "Has an array the same elements as before?: True\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "# random.seed(3)\n",
    "\n",
    "arr = [random.randint(-100, 100) for _ in range(random.randint(1, 20))]\n",
    "k = random.randrange(1, len(arr) + 1)\n",
    "x = random.randint(-100, 100)\n",
    "\n",
    "# arr = [-94, -74, -67, -33, -24, -21, -4, 45, 52, 75, 88, 97]\n",
    "# x = -44\n",
    "# k = 9\n",
    "\n",
    "sorted_arr = sorted(arr)\n",
    "print(\"Sorted arr:\", sorted_arr, sep='\\n')\n",
    "print('x value:', x)\n",
    "print('k value:', k)\n",
    "print(\"Expected:\", sorted_arr[k-1] >= x)\n",
    "print(\"Result:  \", is_kth_val_gt_or_eq_x(arr, k, x))\n",
    "print(\"Arr after calling function:\", arr, sep='\\n')\n",
    "print(\"Has an array the same elements as before?:\", not set(arr).symmetric_difference(sorted_arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OK!\n"
     ]
    }
   ],
   "source": [
    "for _ in range(100_000):\n",
    "    arr = [random.randint(-100, 100) for _ in range(random.randint(1, 20))]\n",
    "    k = random.randrange(1, len(arr) + 1)\n",
    "    x = random.randint(-100, 100)\n",
    "    \n",
    "    sorted_arr = sorted(arr)\n",
    "    \n",
    "    if (sorted_arr[k-1] >= x) is not is_kth_val_gt_or_eq_x(arr, k, x):\n",
    "        print('Failed for:')\n",
    "        print('k:', k)\n",
    "        print('x:', x)\n",
    "        print(arr)\n",
    "        break\n",
    "else:\n",
    "    print(\"OK!\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}